package Sort;

/**
 * @author yyq
 * @create 2021-11-05 20:43
 * 堆排序
 * 要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。
 * 复习顺序二叉树的特点
 * 1) 顺序二叉树通常只考虑**完全二叉树 **
 * 2) 第 n 个元素的左子节点为  **2 * n + 1 **
 * 3) 第 n 个元素的右子节点为 **2 * n + 2 **
 * 4) 第 n 个元素的父节点为 **(n-1) / 2**
 * 5) n : 表示二叉树中的第几个元素(按 0 开始编号如图所示)
 *
 *
 * 实现堆排序
 * 1 首先形成大顶堆 即最大的元素在最上层
 * 2 去除大顶堆顶部元素 把最后一个元素放到顶部
 * 3 在形成大顶堆
 * 4 依次循环直到数组为空
 */
public class Heapsort {
    public static void main(String[] args) {

        int[] a={2,4,6,8,5,9};
        heapsort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
            }
    public  static void  heapsort(int a[]){
        int l=a.length;
        int[] temp = a.clone();
        int i=0;
        while(true){
            if(l==0) break;  //数组长度==0
            reHeap(temp,l);  //构建成大顶堆
            a[i]=temp[0];    //将大顶堆最大值赋予
            temp[0]=temp[l-1]; //将最后一个值成为大顶堆堆顶
            i++;
            l--;
        }

    }
    //继续与父节点比较
    public static void compareParent(int[] a,int i){
        //继续向上比较
        int index=i;
        while(true){
            if(index==0) break;
            //大于父节点
            if(a[index]>a[(index-1)/2]){
                int temp1=a[index];
                a[index]=a[(index-1)/2];
                a[(index-1)/2]=temp1;
                index=(index-1)/2;
            }else {
                break;
            }

        }
    }

    public static void reHeap(int a[],int l){
        //这里的l是长度不是最后一个元素坐标
        //依次循环到最后一个节点
        for (int i = 0; i < l; i++) {
            int leftChild=2*i+1;
            int rightChild=2*i+2;

            //查看是否存在左右孩子,只用判断是否存在左孩子即可，不存在即结束
            if(leftChild>=l) return;

            //因为最后一个节点可能没有右孩子
            //情况一 左右孩子都有
            if(rightChild<l){

                //如果节点小于左右孩子节点, 让左右节点最大的上去
                if(a[i]<a[leftChild] || a[i]<a[rightChild]){
                    if( a[leftChild] >= a[rightChild]){
                        int temp=a[i];
                        a[i]=a[leftChild];
                        a[leftChild]=temp;
                        //继续向上比较
                        compareParent(a,i);
                    }else {
                        int temp=a[i];
                        a[i]=a[rightChild];
                        a[rightChild]=temp;

                        //继续向上比较
                        compareParent(a,i);

                    }
                }
            }else {
                //情况二 只有左孩子
                if(a[i]<a[leftChild]){
                    int temp=a[i];
                    a[i]=a[leftChild];
                    a[leftChild]=temp;
                    //继续向上比较
                    compareParent(a,i);
                }
            }

        }
    }


}
